The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:
Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.
If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
In [1]:
N = 100000
K = 10000
rad = [1]*(N+1)
for p in range(2, N+1):
if rad[p] == 1:
for k in range(p, N+1, p):
rad[k] *= p
print(sorted([[rad[n],n] for n in range(1,N+1)])[K-1][1])
In [ ]: